Kate commitments
1.概要
1.1多項式コミットメント方式とは?
証明者が多項式へのコミットメントを計算することができる方式で、この検証者は後に任意の位置で開く(open)ことができるという特性を持ち、証明者は、ある位置での多項式の値が主張された値と等しいことを示すだけでよい
1.2Merkle treesとの比較
Merkle treesでは深さ$ dを使い、ベクトル（つまり固定長の要素のリスト）へのコミットメント$ a_0,...a_{2^d-1}を計算できる
$ d個のhashを使って、ある要素$ a_iが$ i番目におけるこのベクトルのメンバーであることを証明できる
実際にマークルツリーから多項式コミットメントを行うことができる。
$ p_iは多項式の係数としたとき次数$ nの多項式$ p(X)は $ p(X)=\sum_{i=0}^{n}{p_i}{X^i}にて表される
$ a_i=p_iを設定しその係数のマークルルートを計算することで次数$ n= 2^d-1の多項式にコミットできる。
評価を証明するとは、証明者がいくつかの$ z について検証者に$ p(z)=y を示したいということなので
証明者は、検証者にすべての$ p_iを送り、検証者が$ p(z)は確かに$ yであることを計算することで検証できる
しかし、この手法には以下のようにいくつかの問題がある。
コミットメントサイズは単一のハッシュ（マークルルート）で、十分なセキュリティの暗号化ハッシュには、通常256ビット(32バイト)必要になる
評価を証明するために証明者は多項式の係数$ p_iを全ての$ iについて送信する必要がある。なので、証明サイズが多項式の次数に比例するうえ、線形化する計算が必要になる。
$ p(z)=\sum_{i=0}^{n}{p_i}{z^i}より$ zにおける多項式を評価すること
このスキームは、多項式について何も隠していないので証明者は、多項式全体を明確な係数ごとに送信することになる
このような問題に対し、kateスキームを使うと
コミットメントサイズは、ペアリング可能な楕円群の1つの群要素で済む
例えば、BLS12_381の場合、48バイト
証明サイズは、多項式のサイズとは関係なく、常に1つの群要素のみ。検証も、多項式の大きさとは関係なく、多項式の次数がどうであれ、2つのグループの乗算と2つのペアリングで十分
多項式をほとんど隠すことができる。実際、無限の多項式がまったく同じKate commitmentを持つことになる。しかし、完全に隠れるわけではなく、多項式を推測することができれば、どの多項式がコミットされているかを知ることができる
例えば、それが非常に単純であったり、可能な多項式の小さなセットに含まれていたりすることで
さらに、任意の数の評価に対する証明を1つのグループ要素にまとめることが可能で、これらの特性により、Kate commitmentは、PLONKやSONICなどのゼロ知識証明システム、そしてベクトル・コミットメントに応用できる。
2.楕円曲線とペアリングについて
2.1Trusted setup
秘密の値$ sからなる要素$ [s^i]$ _1と$ [s^i]$ _2は$ i=0,...,n-1の証明と検証について利用することができる
この秘密の設定を取得する1つの方法は、エアギャップされたコンピューターに乱数$ s、全てのグループ要素$ [s^i]$ _zを計算させ
それらの要素を送信し、その後にコンピュータを破棄すれば、秘密を守ったまま、誰も手がつけれなくなる。
しかし、コンピュータは破棄できても、そのコンピュータを操作していた人が$ sを知ることができるため脆弱性が残る
そもそも、コンピュータを破棄するのはもったいないよね...
実際には、複数のコンピュータによってmultiparty computation（MPC）を介して実装され、これらのグループ要素を作成する
単一のコンピュータが秘密を知ることはなく、すべてのコンピュータが秘密を明かすために共謀しなければならない
ランダムにグループ要素$ [s]$ _1（sは不明）を選んで、そこから他のグループ要素を計算する、ということはできない。
つまり、sを知らずに$ [s^2]$ _1などを計算することは不可能
これにより、証明者、検証者を含め、誰もTrusted Setupのグループ要素から$ sが何なのか見つけることは不可能になった
$ sは$ F_pの要素であるが証明者はその値が何なのかはわからない。与えられた要素で特定の計算しかできない。
例えば、$ c[s^i]$ _1=$ cs^iG=$ [cs^i]$ _1のような計算は楕円曲線の乗算から計算できるし、楕円曲線上の点を追加することで、以下のような計算もできる。
$ c[s^i]$ _1+$ d[s^j]$ _1=$ (cs^i+ds^j)G=$ [cs^i+ds^j]$ _1
実際には、もし$ p(X)=\sum_{i=0}^{n}{p_i}{X^i}が多項式の場合、証明者は以下の式を計算することができる
$ p(s)$ _1=$ [\sum_{i=0}^{n}{p_i}{s^i}]$ _1=$ \sum_{i=0}^{n}{p_i}[{s^i}]$ _1
このTrusted Setupを使えば、誰もが、(誰も知らない)ある秘密の点sで多項式を評価することができる
自然数として出力を取得しないことを除いて、楕円曲線点$ [p(s)]$ _1=$ p(s)Gのみを取得するが、これがとても強力であることがわかる
3.Kate commitment
多項式$ p(X)のコミットメント要素を$ C=[p(s)]$ _1と表すとする。
このとき証明者は$ sを知らずに、同じcommitmentを持つ他の多項式$ q(X)(≠p(X))を見つける事ができるのだろうか？要するに$ [p(s)]$ _1?=$ [q(s)]$ _1が成り立つのか？という疑問が出てくる。
この式が成り立つとすれば、$ [p(s)-q(s)]$ _1$ =[0]$ _1つまり$ p(s)-q(s)=0であることを意味する
この疑問について考える
ここで、$ r(X)=p(x)-q(x)が多項式である場合、$ p(X)≠q(X)なのでこれは定数ではない。
次数nの非定数多項式は最大でn個のゼロを持つことができるというのはよく知られた事実らしい
これは、$ r(z)=0の場合、$ r(X)は線形因子$ X-zで割り切れるから
ゼロごとに1つの線形因子で割り切れ、割り切るごとに次数が1つずつ減るので、n以上のゼロは存在しない。
証明者は$ sについて知らないので、$ p(X)-q(X)=0をできるだけ多くの点で作成することが$ p(s)-q(s)=0を実現する唯一の方法である。
つまり、総当たり攻撃によって、$ p(X)-q(X)=0が成り立つ点を探索していく
しかし、彼らはせいぜいn箇所でそれを行うので、成功する可能性は非常に低い
$ nは曲線$ pの次数よりはるかに小さいので、$ sが$ p(X)=q(X)を作るために選んだ点の一つになる確率は極めて小さい
この確率を直感的に理解するために、現在存在する最大のTrusted Setup($ n=2^{28})を使用すると仮定して、カーブオーダ$ p≈2^{256}と比較してみる。
すると、攻撃者が可能な限り多くの点（$ n=2^{28}点）で$ p(X)と一致するように細工した任意の多項式$ q(X)が、同じコミットメント（$ p(s)=q(s)）になる確率は、$ 2^{28}/2^{256}=2^{28-256}≒2・10^{-69}になる
これは無視できるほど低い確率であり、実際には攻撃者はこれをやり遂げることはできないと言える
確率的安全性
1つのユニークな多項式にコミットする方法、つまり同じコミットメント$ C=[p(s)]$ _1を持つ多項式は数多く存在するが、実際に計算することは不可能だということがわかった
暗号学者はこれをComputationally bindingと呼ぶらしい
3.1多項式の乗法
しかし、実際に多項式全体を検証者に送ることなく、このコミットメントを「開く」機能がまだない。
これを実現するためには、ペアリングを使う
いまのところ、例えば、$ p(X)に対するコミットメントとして$ [p(s)]$ _1を計算することができ、また、$ p(X)と$ q(X)の2つのコミットメントを加えて、$ p(X)+q(X)の複合的なコミットメントはできた。
$ [p(s)]_1+[q(s)]_1=[p(s)+q(s)]_1
足りないのは、2つの多項式を掛け合わせる能力。つまり、加算(乗算)である
もしそれができれば、多項式の素晴らしい特性を利用して、欲しいものを実現することができまる
楕円曲線自体ではこのようなことはできないが、幸運なことにペアリングではそれができる
$ e([a]_1,[b]_2] =e(G,H)^{(ab)}=[ab]_T
ここで、$ [x]_T=e(G,H)^x という新しい表記を導入する
したがって，残念ながら，2つのフィールド要素を楕円曲線内で掛け合わせて，その積を楕円曲線要素として得ることはできない
これは，いわゆる完全同型暗号（FHE）の性質であり，楕円曲線は加法的にしか同型ではない
しかし、2つのフィールド要素を異なる曲線（1つは$ G_1，もう1つは$ G_2）でコミットすると，2つのフィールド要素を掛け合わせることができ，その結果，出力は $ G_Tの要素になる。
多項式が$ X-zで割り切れるということは、$ zにゼロがあるということ。
これは、ある多項式$ q(X)に対して$ p(X)=(X-z)・q(X)と書けるということであり、明らかに$ X=zでゼロになる
$ p(z)=yを証明したいとする。ここでは、多項式$ p(X)-yを使う。
この多項式は$ zで明らかにゼロなので、線形因子に関する知識を使うことができ、多項式$ p(X)-yを線形因子$ X-zで割ったものを$ q(X)とする。
つまり
$ q(x)=\frac{p(X)-y}{X-z}
これは$ q(X)(X-z)=p(X)-yと同義
3.2Kate proofs
$ p(z)=yを評価するKate proofは$ π=[q(s)] $ _1と定義される
多項式へのコミットメント$ p(X)は$ C=[p(s)]$ _1と定義してた
検証者は、次の式を使用してこの証明をチェックする
$ e(π, [ s-z]_2 )=e(C-[y]_1,H)
検証者は上式の$ [ s-z]_2 を計算できる。なぜなら、これはtrusted setupから生成された要素$ [ s]_2 と多項式が評価される点の コンビネーションに過ぎないから。同様に、主張された値$ p(z) として$ y を知っているので、$ [ y]_1 も計算できる。
では、なぜこのチェックで$ p(z)=y、より正確には$ zで評価される$ Cがコミットされた多項式が$ yであることを検証者に確信させることができるのだろうか？
この段階で、二つの要素について評価が必要である
Correctness:証明者が定義した通りの手順を踏めば、チェックアウトする証明を作成できること
soundness:「正しくない」証明ができないという性質で、ある$ y′≠yに対して$ p(z)=y′と検証者を騙すことはできない
ペアリンググループで方程式を書き出すことから始めましょう。
$ [ q(s)・(s-z)]_T = [p(s)-y]_T
$ q(X)(X-z)=p(X)-yが、誰も知らないランダムな点$ sで評価されているだけ
では、証明者が偽の証明を作ることができない、健全な証明であることをどうやって知ることができるでしょうか？
これを多項式で考えてみましょう。もし、証明者が、私たちが考えたような方法で証明を作ろうとすると、$ p(X)-y′を$ X-zでどうにかして割らなければなりません。しかし、$ p(z)-y′はゼロではないので、必ず余りが出てしまうため、多項式の除算を行うことはできません。つまり、これは明らかにうまくいきません。
そこで、楕円群で直接計算してみることにします。もしも、あるコミットメント $ Cに対して、楕円群の要素を計算することができるとしたら
$ π_{Fake} = (C-[y']_1 ) ^{\frac{1}{s-z}}
これができれば、当然、何でも証明することができる。直感的には、$ sを含む何かで指数化しなければならないが、$ sについて何も知らないので、これは難しい。これを厳密に証明するには、ペアリングを用いた証明に関する暗号的な仮定、いわゆるq-strong SDH仮定が必要である。
3.3Multiproofs
ここまで、ひとつの点における多項式評価について見てきた。
任意の次数の多項式（例えば$ 2^{28}）がある時点である値をとることを、単一のグループ要素（例えばBLS12_381では48バイト）を送信するだけで示すことができます。
Merkle木を多項式の約束事として使用するおもちゃの例では、$ 2^{28}個の要素（多項式のすべての係数）を送信する必要がありました。
ここでは、さらに一歩進んで、任意の数の点で多項式を評価し、1つの群要素だけを使ってこれを証明できることを示す。
そのために補間多項式の概念を導入する必要がある。
例えば、k個の点のリスト$ (z_0,y_0),(z_1,y_1),...,(z_{k-1},y_{k-1})があるとする
すると、これらの点をすべて通過するkより小さい次数の多項式が必ず見つかる。これを確認する一つの方法は、ラグランジュ補間を用いることで、この多項式の明示的な公式を得ることができる
$ I(X)= \sum ^{k-1}_{i=0}{y_1}\prod_{{j=0},{j≠i}}^{k-1}\frac{X-z_j}{z_i-z_j}
ここで、p(X)がこれらの点をすべて通過することがわかっているとします。
すると、多項式$ p(X)-I(X)は、各$ z_0,z_1,...,z_{k-1}で明らかに0になります。これは、すべての線形因子$ (X-z_0),(X-z_1),...(X-z_{k-1}で割り切れることを意味しています。これらをまとめて、いわゆるゼロ多項式である
$ Z(X)=(X-z_0)・(X-z_1)・・・(X-z_{k-1})
これで、商が計算できる
$ q(x)=\frac{p(X)-I(X)}{Z(X)}
なお、$ p(X)-I(X)は、$ Z(X)のすべての線形因子で割り切れるので、これは可能です。
評価$ (z_0,y_0),(z_1,y_1),...,(z_{k-1},y_{k-1})のKate proofを定義できました。
さて、これを確認するためには、検証者は、補間多項式 $ I(X) とゼロ多項式$ Z(X) を計算する必要があります。これを使って、$ [Z(s)]_2 と$ [I(s)]_1 を計算することで、ペアリング方程式を検証することができます。
$ e(π,[Z(s)]_2) = e(C-[I(s)]_1,H)
ペアリンググループで方程式を書き出すことにより、シングルポイントケイト証明と同じ方法でチェックアウトすることを簡単に確認できます。
$ [q(s)・Z(s)]_T = [p(s)-I(s)]_T
1つのグループ要素を提供するだけで、いくつでも評価を証明できます。100万でも証明できます。これらすべての評価を証明するのはわずか48バイトです。
ベクトルコミットメントとしてのKate
Kate commitmentは、多項式コミットメントとして設計されているが、非常に優れたベクトルのコミットメントも可能
ベクトル・コミットメントは、ベクトル$ a_0,...,a_{n-1}にコミットし、ある$ iに対して$ a_iにコミットしたことを証明することができること
その方法として、まず、すべての$ iに対して$ p(i)=a_iと評価される多項式を$ p(X)とする。
このような多項式があることはわかっており、例えばラグランジュ補間を用いて計算することができる
$ P(X)= \sum ^{n-1}_{i=0}{a_1}\prod_{{j=0},{j≠i}}^{n-1}\frac{X-j}{i-j}
この多項式を使えば，1つのグループ要素(48バイト)だけで，ベクトルの任意の数の要素を証明することができる。
Merkleツリーと比較して、証明サイズの観点からこの方法がどれほど効率的かに注目すると、Merkleの証明では、1つの要素を証明するだけでも$ log nハッシュが必要になるので、違いは明らか
参考文献